package gold.digger;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC172 {


    public int trailingZeroes(int n) {
        return n < 5 ? 0 : n / 5 + trailingZeroes(n / 5);
    }


    public int trailingZeroesT(int n) {
        int res = 0;
        for (int i = 5; i <= n; i += 5) {
            res += getCountableFive(i);
        }

        return res;
    }

    public int getCountableFive(int num) {
        int count = 0;
        while (num % 5 == 0) {
            ++count;
            num /= 5;
        }

        return count;
    }

    public static void main(String[] args) {
        LC172 an = new LC172();
        long startTime = System.currentTimeMillis();
        System.out.println(an.trailingZeroesT(1808548329));
        long fir = System.currentTimeMillis();
        System.out.println("time: " + (fir - startTime) + " ms");
        System.out.println(an.trailingZeroes(1808548329));
        System.out.println("time: " + (System.currentTimeMillis() - fir) + " ms");
    }
}
